Concomitant with the development of high speed digital data processing systems has been the need for intercomponent communication schemes by way of which each of the components that make up an overall system may communicate with one another. One of the present trends in digital communication systems is the use of a distributed network communication system. Typically, a distributed communication network contains a bus over which data, clock, and control signals are conveyed, commonly shared by each component of the system. Through appropriate bus communication interface or adapter units located between a system device (usually including a CPU) and the shared bus, messages are buffered, transmitted, and received.
Within such a digital communication system, messages may be transmitted in a synchronous manner, as by way of a prescribed TDM transmission scheme, or asynchronously, usually on a first come-first served/priority basis. The former approach is usually implemented to afford each device an opportunity to send a message within a recurring transmission time slot. A major drawback to this scheme, however, it its inefficiency, since not all devices may desire to transmit and, as a result, the bus is wastefully tied-up by idle time slots. The asynchronous approach seeks to obviate this drawback by awarding bus occupancy time on the basis of need (to communicate) so that the operational capacity of the bus may be maximized. In order to accomplish this objective, however, some means must be provided to ensure that only a single device may transmit at a time; otherwise, transmissions from plural devices would interfere with one another, or collide, and thereby prevent the successful completion of any intended communication.
For this purpose, there have been developed, in the prior art, schemes for effectively examining the communication link to the intended receiver to determine whether or not the link is busy, namely, whether or not the transmission of a communication to another device would be successful. For example, in the U.S. Pat. No. to Miu et al 4,050,097, there is described a bus communication system in which seizure of a bus by more than one device distributed along the bus is prevented by a priority lockout scheme. In accordance with this patented system, each device that may communicate is assigned a priority. When any device desires to communicate with another device, it requests that the bus be granted to it by way of a bus request signal sent over a bus request line. If no other device wishes to transmit, then the requesting device is granted use of the bus, all other devices being prevented from sending messages or being locked-out for the duration of the communication. Should more than one device attempt to use the bus at the same time, by virtue of an established priority scheme, that includes substantial priority assignment hardware, only the device having the higher priority is granted immediate use of the bus, with lower priority devices having to wait their turn. In effect, through separate fixed priority connections and logic, the patented system always effects a housekeeping routine of prioritizing transmission requests and assigning the order of use of the bus before each message is sent. Therefore, while this approach provides a safeguard against collisions, it requires substantial lockout circuitry and the elapse of a prescribed pretransmission wait time for each message sent.
In the U.S. Pat. No. to Duke et al 4,038,644, there is described a processor communication system in which there is a separate bus adapter for each unit, with an individual bus busy line associated with every adapter. When one of the units wishes to communicate with another unit, it sends a request to the local bus adapter of the receiving unit to determine whether or not the receiver unit is busy. If the receiver is not busy, a busy identification flag is set on the busy line of the receiver unit, informing the receiver that a message will be sent to it from the transmitter and also informing all other devices connected to the bus that they cannot presently communicate with the receiver (since a transmission is presently being prepared to be sent to it). Each bus adapter is assigned a priority in the system, similar to the system of Miu et al, discussed above, and the priority scheme is used to prevent simultaneous seizure.
The U.S. Pat. No. to Driscoll 3,445,822 describes a common bus interconnection network in which any device may seize the bus to communicate with another device. Prior to Seizure of the bus, however, each unit generates a seizure code, which is compared with a prescribed code to determine whether or not the bus is available. If the two codes do not coincide, the requesting device is informed that another unit is attempting to seize the bus and that the device must wait until a match occurs.
In each of the above-described prior art systems the collision avoidance schemes are complex, requiring a substantial amount of hardware, and the bus interface communication units are required to perform a significant amount of housekeeping and transmission preparation tasks before a message is actually sent. As a result, use of the bus is delayed and the efficiency of the system is decreased.
As opposed to the strict collision avoidance systems, as described above, there have also been developed schemes which, after a brief check of the bus, operate to immediately send a message over the bus, if the bus has not already been seized, but which permit collisions to occur, necessitating a retransmission. Such systems are described in the publications: "Ethernet: Distributed Packet Switching for Local Computer Networks" by R. M. Metcalfe et al, Communications of the ACM, July 1976, Vol. 19, No. 7, pages 395-403, and an article entitled "Acknowledging Ethernet" by M. Tokoro et al, pages 320-325. Basically, in accordance with an "Ethernet" type of scheme, the bus is checked for busy status prior to each transmission. Assuming the bus is quiet, then after a brief wait interval, if the bus is still quiet, a message, or data packet, is transmitted. If the message collides with another packet, retransmission is carried out according to a prescribed collision control algorithm. In order to detect the occurrence of a collision, each transceiver contains an interference detector. The interference detector monitors the bus and compares what is sees to what its device is supposed to be transmitting. A difference in the bit values of the two quantities, representative of a collision, causes the transmitter to truncate its message and temporarily jam the bus, thereby informing the other participants in the collision of the interference. A transmitting device recovers from a detected collision by aborting the transmission and retransmitting the message after a prescribed dynamically chosen random time period. Thus, as compared to the previously described prior art apparatus, an "Ethernet" type of bus collision scheme attempts to be more efficient by compromising between pretransmission housekeeping and the need to retransmit. However, in so doing, the system employs a bus collision monitor that adds to the complexity of the full duplex "Ethernet" scheme.